#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        for (int i = 0; i < n;)
        {
            int x = nums[i];
            for (int j = i + 1; j < n;)
            {
                int begin = j + 1, end = n - 1;
                long long z = (long long)target - nums[i] - nums[j];
                while (begin < end)
                {
                    int sum = nums[begin] + nums[end];
                    if (sum < z) begin++;
                    else if (sum > z) end--;
                    else
                    {
                        ret.push_back({ nums[i],nums[j],nums[begin],nums[end] });
                        begin++;
                        while (begin < end && nums[begin] == nums[begin - 1]) begin++;
                        end--;
                        while (begin < end && nums[end] == nums[end + 1]) end--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};
int main()
{
    vector<int> v({ 1,0,-1,0,-2,2 });
    vector<vector<int>> v1(Solution().fourSum(v, 0));
    for (auto e : v1)
    {
        for (auto x : e)
        {
            cout << x << " ";
        }
        cout << endl;
    }
    
	return 0;
}
/*
题目链接:https://leetcode.cn/problems/4sum/
*/